class Solution {
private:
    static const int maxn = 201;
    vector<vector<char>> board;
    string word;
    bool visited[maxn][maxn];
    bool dfs(int i, int j, int word_index){
        if(visited[i][j] || word[word_index] != board[i][j]) return false;
        else if(word_index == word.length()-1) return true;
        visited[i][j] = true;
        bool ret = false;
        if(i>0) ret |= dfs(i-1, j, word_index+1);
        if(!ret && i<board.size()-1) ret |= dfs(i+1, j, word_index+1);
        if(!ret && j>0) ret |= dfs(i, j-1, word_index+1);
        if(!ret && j<board[0].size()-1) ret |= dfs(i, j+1, word_index+1);
        visited[i][j] = false;
        return ret;
    }
public:
    bool exist(vector<vector<char>>& board, string word) {
        this->board = board;
        this->word = word;
        bool ret = false;
        for(int i=0; i<board.size(); i++){
            for(int j=0; j<board[0].size(); j++){
                if(!ret)
                    ret |= dfs(i, j, 0);
            }
        }
        return ret;
    }
};